package leet_code;

import java.util.HashMap;
import java.util.Map;

/**
 * 字串相关问题
 */
public class A_4_SubString {

    /**
     * 560. 和为 K 的子数组
     * https://leetcode.cn/problems/subarray-sum-equals-k/?envType=study-plan-v2&envId=top-100-liked
     * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
     * <p>
     * 示例 1：
     * 输入：nums = [1,1,1], k = 2
     * 输出：2
     * <p>
     * 示例 2：
     * 输入：nums = [1,2,3], k = 3
     * 输出：2
     * <p>
     * 提示：
     * 1 <= nums.length <= 2 * 10^4
     * -1000 <= nums[i] <= 1000
     * -10^7 <= k <= 10^7
     *
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum(int[] nums, int k) {
//        方法一：暴力法
//        int count = 0;
//        int len = nums.length;
//        for (int left = 0; left < len; left++) {
//            int sum = 0;
//            // 区间里可能会有一些互相抵销的元素
//            for (int right = left; right < len; right++) {
//                sum += nums[right];
//                if (sum == k) {
//                    count++;
//                }
//            }
//        }
//        return count;
//        -------------------------------------
//        方法二：前缀和
        int len = nums.length;
        int[] preSum = new int[len + 1];
        //构建前缀和数组，什么是前缀和，当前位置之前所有元素之和
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        //遍历数组
        int count = 0;
        for (int left = 0; left < len; left++) {
            for (int right = left; right < len; right++) {
                if (preSum[right + 1] - preSum[left] == k) {
                    count++;
                }
            }
        }
        return count;
//        -------------------------------
//        // key：前缀和，value：key 对应的前缀和的个数
//        Map<Integer, Integer> preSumFreq = new HashMap<>();
//        // 对于下标为 0 的元素，前缀和为 0，个数为 1
//        preSumFreq.put(0, 1);
//
//        int preSum = 0;
//        int count = 0;
//        for (int num : nums) {
//            preSum += num;
//
//            // 先获得前缀和为 preSum - k 的个数，加到计数变量里
//            if (preSumFreq.containsKey(preSum - k)) {
//                count += preSumFreq.get(preSum - k);
//            }
//
//            // 然后维护 preSumFreq 的定义
//            preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
//        }
//        return count;
    }


    /**
     * 239. 滑动窗口最大值
     * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
     * 返回 滑动窗口中的最大值 。
     * <p>
     * 示例 1：
     * 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
     * 输出：[3,3,5,5,6,7]
     * 解释：
     * 滑动窗口的位置                最大值
     * ---------------               -----
     * [1  3  -1] -3  5  3  6  7       3
     * 1 [3  -1  -3] 5  3  6  7       3
     * 1  3 [-1  -3  5] 3  6  7       5
     * 1  3  -1 [-3  5  3] 6  7       5
     * 1  3  -1  -3 [5  3  6] 7       6
     * 1  3  -1  -3  5 [3  6  7]      7
     * <p>
     * 示例 2：
     * 输入：nums = [1], k = 1
     * 输出：[1]
     * <p>
     * <p>
     * 提示：
     * 1 <= nums.length <= 10^5
     * -10^4 <= nums[i] <= 10^4
     * 1 <= k <= nums.length
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) {
            return nums;
        }
        //获取
        int[] res = new int[nums.length - k + 1];
        int max = nums[0];
        int maxEqCount = 1;
        for (int j = 1; j < k; j++) {
            if (max == nums[j]) {
                maxEqCount++;
            } else if (max < nums[j]) {
                max = nums[j];
                maxEqCount = 1;
            }
        }
        res[0] = max;

        for (int i = 1; i < nums.length - k + 1; i++) {
            //先处理右侧，再处理左侧
            //右侧：当大于最大值时，设置最大值并重置最大值个数
            if (max < nums[i + k - 1]) {
                max = nums[i + k - 1];
                maxEqCount = 1;
            } else if (max == nums[i + k - 1]) {
                maxEqCount++;
            }

            //左侧：当移除的值等于最大值时,最大值被移除
            if (max == nums[i - 1]) {
                maxEqCount--;
            }

            //当最大值被移除时，需要重新对数组进行排序
            if (maxEqCount == 0) {
                max = nums[i];
                maxEqCount = 1;
                for (int j = i + 1; j < i + k; j++) {
                    if (max == nums[j]) {
                        maxEqCount++;
                    } else if (max < nums[j]) {
                        max = nums[j];
                        maxEqCount = 1;
                    }
                }
            }

            res[i] = max;
        }
        return res;
    }

    /**
     * 76. 最小覆盖子串
     * https://leetcode.cn/problems/minimum-window-substring/?envType=study-plan-v2&envId=top-100-liked
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     *
     * 注意：
     * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
     * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
     *
     * 示例 1：
     * 输入：s = "ADOBECODEBANC", t = "ABC"
     * 输出："BANC"
     * 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
     *
     * 示例 2：
     * 输入：s = "a", t = "a"
     * 输出："a"
     * 解释：整个字符串 s 是最小覆盖子串。
     *
     * 示例 3:
     * 输入: s = "a", t = "aa"
     * 输出: ""
     * 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
     * 因此没有符合条件的子字符串，返回空字符串。
     *
     * 提示：
     * m == s.length
     * n == t.length
     * 1 <= m, n <= 10^5
     * s 和 t 由英文字母组成
     *
     * 进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        return null;
    }

    public static void main(String[] args) {
        A_4_SubString subString = new A_4_SubString();

        //滑动窗口最大值
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
//        int[] nums = {1,-1};
//        int k = 1;
//        int[] nums = {7, 2, 4};
//        int k = 2;
//        int[] nums = {9,10,9,-7,-4,-8,2,-6};
//        int k = 5;
        int[] ints = subString.maxSlidingWindow(nums, k);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }
}
